//
// Created by Administrator on 2021/8/10.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    int jump(vector<int> &nums) {
        vector<int> dp(nums.size(), INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < nums.size(); ++i) {
            // 如果这一格能到 那么后面1~nums[i]格都能到
            if (dp[i] != INT_MAX) {
                for (int j = 1; j <= nums[i] and i + j < nums.size(); ++j) {
                    dp[i + j] = min(dp[i + j], dp[i] + 1);
                }
            }
        }
        return dp.back();
        //AC 12%
    }
};

class Solution2 { // 题解 贪心
public:
    int jump(vector<int> &nums) {
        int maxPos = 0, n = (int) nums.size(), end = 0, step = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (maxPos >= i) {
                maxPos = max(maxPos, i + nums[i]);
                if (i == end) { // 到达当前能够到达的最远边界  记录一次跳跃
                    end = maxPos;
                    ++step;
                }
            }
        }
        return step;
    }
};

int main() {
    vector<int> nums{2, 3, 0, 1, 4};
    Solution2 solution;
    cout << solution.jump(nums) << endl;
    return 0;
}
